290. Word Pattern

給定一個模式字串 pattern 和一個句子字串 s，請判斷 s 是否遵循 pattern 給定的模式。

題目條件：
pattern 是一個由小寫字母組成的非空字串，例如 "abba"。
s 是由小寫字母單詞組成且由空格分隔的字串，例如 "dog cat cat dog"。

規則：
pattern 中的每個字母應該對應 s 中的一個單詞。
同一個字母不能對應不同的單詞。
同一個單詞也不能對應不同的字母（雙向映射）。

程式碼

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        hash_map = {}
        s = s.split(" ")
        counter = 0
        
        if len(pattern) != len(s):
            return False

        for char in pattern:
            if hash_map.get(char):
                if hash_map[char] != s[counter]:
                    return False
            else:
                if s[counter] in hash_map.values():
                    return False
                hash_map[char] = s[counter]
            counter += 1
        return True

優化：同時遍歷 pattern 與 s

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        # 將 s 分割為單詞列表
        words = s.split(" ")
        
        # 如果 pattern 和 words 的長度不同，直接返回 False
        if len(pattern) != len(words):
            return False

        # 創建兩個映射字典：pattern -> word 和 word -> pattern
        pattern_to_word = {}
        word_to_pattern = {}

        # 遍歷 pattern 和 words 中的每一個元素
        for char, word in zip(pattern, words):
            # 檢查 pattern 中的字母是否已經有對應的單詞
            if char in pattern_to_word:
                # 如果對應的單詞不同，返回 False
                if pattern_to_word[char] != word:
                    return False
            else:
                # 檢查該單詞是否已經對應到其他字母
                if word in word_to_pattern:
                    return False
                # 建立新的映射
                pattern_to_word[char] = word
                word_to_pattern[word] = char

        # 如果所有條件都符合，返回 True
        return True

3. Longest Substring Without Repeating Characters

給定一個字串 s，請找出不包含重複字符的最長子字串的長度。

解題思路

要解決這個問題，我們可以使用 「滑動視窗（Sliding Window）」 搭配 「哈希表（Hash Map）」 的方式來達到高效的解法。

解題步驟

1. 使用雙指針來表示滑動視窗的邊界
   • 初始化兩個指針 left 和 right，分別表示滑動視窗的左邊界和右邊界。視窗中儲存當前子字串的所有字符。
2. 利用 Hash Map 記錄字符的最後出現位置
   • 使用 Hash Map 來記錄每個字符在字串中最後一次出現的位置，這樣當發現重複字符時，可以透過 Hash Map 確定左指針 left 應該跳到的位置。
3. 移動右指針來擴展滑動視窗
   • 右指針 right 從左到右遍歷整個字串，每遇到一個新字符時，將其加入 Hash Map 中。
4. 處理重複字符
   • 當 right 指針遇到的字符已經存在於滑動視窗中（即該字符已存在於 Hash Map 中，且 hash_map[char] >= left），則表示出現重複字符。
   • 更新左指針 left 到 hash_map[char] + 1，即移動到重複字符的下一個位置。
5. 更新無重複子字串的最大長度
   • 每次調整滑動視窗後，計算當前無重複子字串的長度 right - left + 1，並更新最大長度 max_length。
6. 返回最大長度
   • 遍歷完所有字符後，返回最大長度 max_length 作為結果。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        hash_map = {}  # 使用 Hash Map 記錄字符最後出現的位置
        left = 0  # 左指針初始化
        max_length = 0  # 最大無重複子字串長度

        # 使用右指針遍歷字串
        for right, char in enumerate(s):
            # 如果字符已經出現在 Hash Map 中，並且其索引大於等於左指針，移動左指針
            if char in hash_map and hash_map[char] >= left:
                left = hash_map[char] + 1

            # 更新當前字符在 Hash Map 中的位置
            hash_map[char] = right

            # 計算當前無重複子字串的長度，並更新最大長度
            max_length = max(max_length, right - left + 1)

        return max_length